package com.fenqing.leetcode.code.t600_700;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

/**
 * @author fenqing
 */
public class Topic744 extends Topic {

    /**
     * 构造器
     * @param input1 输入1
     * @param input2 输入2
     */
    public Topic744(String input1, String input2) {
        super(input1, input2);
    }

    /**
     * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
     * 在比较时，字母是依序循环出现的。举个例子：
     * 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
     * 示例 1：
     * 输入: letters = ["c", "f", "j"]，target = "a"
     * 输出: "c"
     * 示例 2:
     * 输入: letters = ["c","f","j"], target = "c"
     * 输出: "f"
     * 示例 3:
     * 输入: letters = ["c","f","j"], target = "d"
     * 输出: "f"
     * 提示：
     * 2 <= letters.length <= 104
     * letters[i] 是一个小写字母
     * letters 按非递减顺序排序
     * letters 最少包含两个不同的字母
     * target 是一个小写字母
     * @param letters letters
     * @param target target
     * @return return
     */
    @Execute
    public char nextGreatestLetter(char[] letters, char target) {
        //寻找左边比target小，右边比target大的一个下标
        int left = 0, right = letters.length - 1;
        while (left < right) {
            int midIdx = (left + right) >> 1;
            char ch = letters[midIdx];
            boolean leftOk;
            if (midIdx == 0) {
                leftOk = true;
            } else {
                leftOk = letters[midIdx - 1] < target;
            }
            if (leftOk && ch > target) {
                return ch;
            } else if (ch > target){
                right = midIdx;
            } else {
                left = midIdx + 1;
            }
        }
        return letters[left] <= target ? letters[0] : letters[left];
    }

    public static void main(String[] args) {
        Topic744 topic744 = new Topic744("""
                ["c", "f", "j"]
                """, "j");
        char run = topic744.run();
        System.out.println(run);
    }

}
